/*
https://leetcode-cn.com/problems/sort-list/solution/pai-xu-lian-biao-by-leetcode-solution/
 */
public class Solution148 {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode sortList(ListNode head) {
        if (head==null){
            return null;
        }
        int len=0;
        ListNode first=head;
        while (first!=null){
            len++;
            first=first.next;
        }
        ListNode f=new ListNode(-1,head);
        for (int l=1;l<len;l=l*2){
            ListNode pre=f,cur=f.next;
            while (cur!=null){
                ListNode c=cur;
                int flag=-1;
                for (int i=0;i<l;i++){
                    c=c.next;
                    if (c==null){
                        flag=1;
                        break;
                    }
                }
                if (flag==1){
                    break;
                }
                ListNode after=c;
                int lt=0;
                for (int i=0;i<l;i++){
                    after=after.next;
                    lt++;
                    if (after==null){
                        break;
                    }
                }
                ListNode[] tt=merge(cur,l,c,lt);
                tt[1].next=after;
                pre.next=tt[0];
                pre=tt[1];
                cur=after;
            }
        }
        return f.next;
    }

    ListNode[] merge(ListNode l1,int len1,ListNode l2,int len2){
        ListNode f=new ListNode(-1,null);
        int i=0,j=0;
        ListNode l1c=l1,l2c=l2,fc=f;
        while (i<len1 && j<len2){
            if (l1c.val<l2c.val){
                fc.next=l1c;
                l1c=l1c.next;
                fc=fc.next;
                i++;
            }else{
                fc.next=l2c;
                l2c=l2c.next;
                fc=fc.next;
                j++;
            }
        }
        ListNode last=null;
        while (i<len1){
            fc.next=l1c;
            l1c=l1c.next;
            fc=fc.next;
            last=fc;
            i++;
        }
        while (j<len2){
            fc.next=l2c;
            l2c=l2c.next;
            fc=fc.next;
            last=fc;
            j++;
        }
        return new ListNode[]{f.next,last};
    }


    public static void main(String[] args) {
        System.out.println(new Solution148().sortList(new ListNode(-1,new ListNode(5,new ListNode(3,new ListNode(4,new ListNode(0)))))).next.val);
    }
}
